Dense order

 ( Properties Of Binary Relations ) 

In mathematics, a partial order or total order < on a set $X$ is said to be dense if, for all $x$ and $y$ in $X$ for which , there is a $z$ in $X$ such that . That is, for any two elements, one less than the other, there is another element between them. For total orders this can be simplified to "for any two distinct elements, there is another element between them", since all elements of a total order are comparability.

---

Example The as a linearly ordered set are a densely ordered set in this sense, as are the , the , the and the . In fact, every Archimedean ordered ring extension of the integers $\backslash mathbb\{Z\}x$ is a densely ordered set.

On the other hand, the linear ordering on the is not dense.

---

Uniqueness for total dense orders without endpoints Georg Cantor proved that every two non-empty dense totally ordered without lower or upper bounds are order-isomorphic.. This makes the theory of dense linear orders without bounds an example of an ω-categorical theory where ω is the smallest limit ordinal. For example, there exists an order-isomorphism between the and other densely ordered countable sets including the and the . The proofs of these results use the back-and-forth method..

Minkowski's question mark function can be used to determine the order isomorphisms between the quadratic algebraic numbers and the , and between the rationals and the .

---

Generalizations Any binary relation R is said to be dense if, for all R-related x and y, there is a z such that x and z and also z and y are R-related. Formally:

$\backslash forall\; x\backslash \; \backslash forall\; y\backslash \; xRy\backslash Rightarrow\; (\backslash exists\; z\backslash \; xRz\; \backslash land\; zRy).$ Alternatively, in terms of composition of R with itself, the dense condition may be expressed as R ⊆ ( R ; R).Gunter Schmidt (2011) Relational Mathematics, page 212, Cambridge University Press

Sufficient conditions for a binary relation R on a set X to be dense are:

• R is reflexive;
• R is coreflexive;
• R is quasireflexive;
• R is left or right Euclidean; or
• R is symmetric and semi-connex and X has at least 3 elements.

None of them are necessary. For instance, there is a relation R that is not reflexive but dense. A Empty relation and dense relation cannot be antitransitive.

A strict partial order < is a dense order if and only if < is a dense relation. A dense relation that is also transitive is said to be idempotent.

---

See also

• Dense set — a subset of a topological space whose closure is the whole space
• Dense-in-itself — a subset $A$ of a topological space such that $A$ does not contain an isolated point
• Kripke semantics — a dense accessibility relation corresponds to the axiom $\backslash Box\backslash Box\; A\; \backslash rightarrow\; \backslash Box\; A$

---

Further reading

• David Harel, Dexter Kozen, Jerzy Tiuryn, Dynamic logic, MIT Press, 2000, , p. 6ff

Post Comment